#include "Sort.h"
#include "SeqStack.h"

void Swap(int *a,int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
void SortPrintInt(int arr[],int64_t size,const char *msg)
{
    if(NULL==arr||size<=0)
    {
        return;
    }
    printf("\n%s\n",msg);
    int64_t i=0;
    for(i=0;i<size;i++)
    {
        printf("[%d] ",arr[i]);
    }
    printf("\n");
}
//*****************冒泡排序********************************
void BubbleSort(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    int64_t count=0;
    int64_t i=0;
    int flag=0;
    for(count=0;count<size-1;count++)
    {
        for(i=0;i<size-count-1;i++)
        {
            if(arr[i]>arr[i+1])
            {
                Swap(&arr[i],&arr[i+1]);
                flag=1;
            }
        }
        if(0==flag)
        {//已经有序
            break;
        }
    }
}
//******************************选择排序***************************
void SeleteSort(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    int64_t i=0;
    int64_t bound=0;
    for(bound=0;bound<size;bound++)
    {
        for(i=bound+1;i<size;i++)
        {
            if(arr[bound]>arr[i])
            {
                Swap(&arr[bound],&arr[i]);
            }
        }
    }
}
//********************************插入排序***********************
void InsertSort(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    int64_t bound=0;
    int64_t i=0;
    for(bound=1;bound<size;bound++)
    {
        int cur=arr[bound];
        for(i=bound;i>0;i--)
        {
            if(arr[i-1]>cur)
            {
                arr[i]=arr[i-1];
            }
            else
            {
                break;
            }
        }
        arr[i]=cur;
    }
}
//*********************************堆排序************************************
void AdjustDown(int arr[],int64_t size,int64_t start)
{
    int64_t parent=start;
    int64_t lchild=start*2+1;
    int64_t rchild=start*2+2;
    int64_t child=lchild;
    while(lchild<size)
    {
        if(rchild<size)
        {
            if(arr[rchild]>arr[lchild])
            {
                child=rchild;
            }
            else
            {
                child=lchild;
            }
        }
        else
        {
            child=lchild;
        }
        if(arr[parent]<arr[child])
        {//如果父节点值小于孩子中的较大的
            Swap(&arr[parent],&arr[child]);
            parent=child;
            lchild=parent*2+1;
            rchild=parent*2+2;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    //1.构造一个大顶堆
    int64_t start=(size-1-1)/2;//从第一个非叶子节点开始调整
    for(;start>=0;start--)//如若此处的size类型为size_t,判断条件不是这样
    {
        AdjustDown(arr,size,start);//进行下沉操作
    }
    //2.依次删除堆顶元素
    int64_t n=size;
    int64_t count=0;
    for(count=size;count>0;count--)
    {
        if(n==0)
        {
            break;
        }
        Swap(&arr[0],&arr[n-1]);
        start=(n-1-1)/2;//此处类型若为size_t就还要加一层判断
        n--;//进行交换了之后，应该将堆的大小进行调整
        for(;start>=0;start--)
        {
            AdjustDown(arr,n,start);
        }
    }
}
//******************************希尔排序****************************
void ShellSort(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    int64_t gap=size/2;
    int64_t i=0;
    int64_t j=0;
    for(;gap>=1;gap=gap/2)
    {
        for(i=gap;i<size;i++)
        {
            int cur=arr[i];
            for(j=i;j>=gap;j=j-gap)
            {
                if(cur<arr[j-gap])
                {
                    arr[j]=arr[j-gap];
                }
                else
                {
                    break;
                }
            }
            arr[j]=cur;
        }
    }
}
//*************************归并排序***************************
void Array(int arr[],int64_t start,int64_t mid,int64_t end,int *buffer)
{
    if(end - start <= 1)
    {
        return;
    }
//    printf("start:%lu,mid:%lu,end:%lu\n",start,mid,end);
    int64_t count=start;//注意：此处的count应该从start开始。而不是从0开始
    int64_t left=start;
    int64_t middle=mid;
    while(left<mid&&middle<end)//此处left应该小于mid而不是middle因为此处的middle在下面已经改了
    {
            if(arr[left]<=arr[middle])
            {
            buffer[count]=arr[left];
            left++;count++;
            }
            else
            {
                buffer[count]=arr[middle];
                middle++;count++;
            }
    }
    
   while(left<mid)
   {
            buffer[count++]=arr[left++];
   }
   while(middle<end)
   {
            buffer[count++]=arr[middle++];
   }
   memcpy(arr,buffer,sizeof(int)*(end));
//   SortPrintInt(arr,10,"一次排序");
//   memcpy(arr+start,buffer+start,sizeof(int)*(end-start));//
}
void _MergeSort(int arr[],int64_t start,int64_t end,int *buffer)
{
    if(end-start<=1)
    {
        return;
    }
    int64_t mid=start+(end-start)/2;
    _MergeSort(arr,start,mid,buffer);
    _MergeSort(arr,mid,end,buffer);
    Array(arr,start,mid,end,buffer);
//    printf("start:%lu,mid:%lu,end:%lu\n",start,mid,end);
//    SortPrintInt(arr,10,"一次排序");
//    这样可以看出来，第一次进行排序了下标为0 1 2,第二次进行排序了3 4 5 ，
//    但是这是一个前闭后开区间，其实都没有将2 的位置进行处理,但是进行0 2 5 归并时，memcpy时却将2的位置进行了拷贝
//    这个时候拷贝2 的位置的就是0,所以可以采用上面的方法,每次进行拷贝时不是从开头拷贝end个而时从start拷贝end-start个；
//    也可以在初始时将buffer进行拷贝为arr数组。
}
void MergeSort(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    int64_t start=0;
    int64_t end=size;
    int *buffer=(int *)malloc(sizeof(int)*size);
    memcpy(buffer,arr,sizeof(int)*size);//此处用不用将buffer进行赋值可以参考上面的解释
    _MergeSort(arr,start,end,buffer);//是一个前闭后开区间
    free(buffer);
}
//*******************归并排序（非递归）*****************
void Array_(int arr[],int64_t start,int64_t mid,int64_t end,int *buffer)
{
    int64_t cur1=start;
    int64_t cur2=mid;
    int64_t index=start;
    while(cur1<mid&&cur2<end)
    {
        if(arr[cur1]<arr[cur2])
        {
            buffer[index++]=arr[cur1++];
        }
        else
        {
            buffer[index++]=arr[cur2++];
        }
    }
    //出循环处理剩下两路中可能有一路还没有遍历完
    while(cur1<mid)
    {
        buffer[index++]=arr[cur1++];
    }
    while(cur2<end)
    {
        buffer[index++]=arr[cur2++];
    }
    memcpy(arr+start,buffer+start,sizeof(int)*(end-start));
}
void MergeSortByLoop(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    int *buffer=(int *)malloc(sizeof(int)*size);
    //memcpy(buffer,arr,sizeof(int)*size);
    int64_t gap=1;
    int64_t i=0;
    for(gap=1;gap<size;gap=gap*2)
    {
        for(i=0;i<size;i=i+gap*2)
        {
            int64_t mid=i+gap;
            int64_t end=i+2*gap;
            if(mid>=size)
            {
                mid=size;
            }
            if(end>=size)
            {
                end=size;
            }
            Array_(arr,i,mid,end,buffer);
        }
    }
    free(buffer);
}
//*******************快速排序*************************
int64_t Partion_0(int arr[],int64_t start,int64_t end)
{
    int key=arr[end-1];
    int64_t left=start;
    int64_t right=end-1;
    while(left<right)
    {
        while(left<right)
        {
            if(arr[left]<=key)
            {
                left++;
            }
            else
            {
                arr[right]=arr[left];
                break;
            }
        }
        while(left<right)
        {
            if(arr[right]>=key)
            {
                right--;
            }
            else
            {
                arr[left]=arr[right];
                break;
            }
        }
    }
    //出循环后left与right相遇
    arr[left]=key;
    return left;
}
int64_t Partion_1(int arr[],int64_t start,int64_t end)
{
    int key=arr[end-1];
    int64_t left=start;
    int64_t right=end-1;
    while(left<right)
    {
        while(left<right)
        {
            if(arr[left]<=key)
            {
                left++;
            }
            else
            {
                break;
            }
        }
        while(left<right)
        {
            if(arr[right]>=key)
            {
                right--;
            }
            else
            {
                break;
            }
        }
        if(left<right)
        {
            Swap(&arr[left],&arr[right]);
        }
        else
        {
            break;
        }
    }
    //出循环后，left与right相等，并且arr[left]一定是大于或者等于key的（因为此处是从左侧开始找比key大的值，可以自己理一下）
    Swap(&arr[end-1],&arr[left]);
    return left;
}
void _QuickSort(int arr[],int64_t start,int64_t end)
{
    if(end-start<=1)
    {
        return;
    }
    int mid=Partion_0(arr,start,end);
    _QuickSort(arr,start,mid);
    _QuickSort(arr,mid+1,end);
}
void QuickSort(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    _QuickSort(arr,0,size);
}
//*************************快速排序（非递归）**********************
void QuickSortByLoop(int arr[],int64_t size)
{
    if(NULL==arr||size<=1)
    {
        return;
    }
    SeqStack stack;
    SeqStackInit(&stack);
    SeqStackPush(&stack,size);
    SeqStackPush(&stack,0);
    SeqStackType tmp=0;
    int64_t start=tmp;
    int64_t end=tmp;
    while(SeqStackGetSize(&stack)!=0)//当栈不为空时，说明还没有遍历完成
    {
       if( SeqStackTop(&stack,&tmp))
       {
        start=tmp;
        SeqStackPop(&stack);
       }
       else
       {
           break;
       }
       if(SeqStackTop(&stack,&tmp))
       {
        end=tmp;
        SeqStackPop(&stack);
       }
       else
       {
           break;
       }
       if(end-start<=1)//注意要判断此处需不需要进行一次快速排序
       {
           continue;
       }
       int64_t mid=Partion_1(arr,start,end);
       SeqStackPush(&stack,end);
       SeqStackPush(&stack,mid+1);
       SeqStackPush(&stack,mid);
       SeqStackPush(&stack,start);
    }
}
